package com.aqie.arithmetic.sort;

import com.aqie.libs.StdRandom;

/**
 * 快速排序
 * 优化
 * 1，切换到插入排序
 * 2，三取样切分
 * 3，熵最优的排序
 */
public class QuickSort extends SortTest{
    @Override
    public void sort(Comparable[] a) {
       // 消除对输入的依赖
        StdRandom.shuffle(a);
        sort(a, 0, a.length - 1);
    }

    private void sort(Comparable[] a, int l, int h) {
        if (h <= l) return;
        int j = partition(a, l, h);
        sort(a, l, j - 1);
        sort(a, j + 1, h);
    }

    private int partition(Comparable[] a, int l, int h) {

        // 数组切分位a[l..i-1]  a[i] a[i+1..h]
        int i = l, j = h + 1;       // 左右扫描指针
        Comparable v = a[l];        // 切分元素
        while (true){
            while (less(a[++i], v)) if (i == h) break;
            while (less(v, a[--j])) if (j == l) break;
            if (i >= j) break;
            exch(a, i, j);
        }
        exch(a, l, j);
        return j;
    }

    public static void main(String[] args) {
        new QuickSort().process(10000);
    }
}
